#include <iostream>
#include <memory>
#include <string.h>
#include <string>
#include <unordered_map>
#include <vector>

// 定义一个全局变量来跟踪当前的调用深度
int g_call_depth = 0;

#define MY_PRINT(fmt, ...) do { \
	printf("%*s", g_call_depth * 2, ""); \
	printf("%s:%d " fmt "\n", __func__, __LINE__, ##__VA_ARGS__) ; \
} while (0)

// 定义宏来增加和减少调用深度
#define ENTER_FUNCTION do { \
	g_call_depth++; \
} while (0)

#define EXIT_FUNCTION do { \
	g_call_depth--; \
} while (0)

// dp_trie_node 定义
// 根节点的为(0)
class dp_trie_node {
public:
	std::unordered_map<char, std::shared_ptr<dp_trie_node>> child_;
	std::shared_ptr<dp_trie_node> parent_;
	void* rule_obj_; // 规则对象
	bool bend_;      // 是否为规则终点
	char c_;         // 当前节点的字符 ,根节点为0

	dp_trie_node(char c, std::shared_ptr<dp_trie_node>& parent)
		: bend_(false)
		  , rule_obj_(NULL)
		  , c_(c)
		  , parent_(parent)
	{
	}
	// 获取树关键字列表
	void get_tree_str(std::string& str)
	{
		if (0 != c_) {
			str.insert(0, 1, c_);
		}
		if (parent_) {
			parent_->get_tree_str(str);
		}
	}
	~dp_trie_node() { }
};

// dp_trie 定义
class dp_trie {
public:
	dp_trie()
	{
		std::shared_ptr<dp_trie_node> n;
		root_ = std::make_shared<dp_trie_node>(0, n);
	}

	/**
	 * @brief 插入规则
	 *
	 * @param rule 规则字符串
	 * @param rule_obj 规则对应的对象
	 * @param back true则rule构建时从后向前构建, 否则从前向后构建
	 *
	 */
	void insert(const std::string& rule, void* rule_obj, bool back = false)
	{
		if (rule.empty()) { // 忽略空规则
			return;
		}
		rules_.push_back(rule);
		auto node = root_;
		size_t len = rule.size();
		size_t start = back ? len - 1 : 0;
		size_t end = back ? static_cast<size_t>(-1) : len;
		int step = back ? -1 : 1;
		for (size_t i = start; i != end; i += step) {
			char c = rule[i];
			if (!node->child_.count(c)) {
				node->child_[c] = std::make_shared<dp_trie_node>(c, node);
				//MY_PRINT("%s:%d child[%c]=%s\n", __func__, __LINE__, c, rule.c_str());
			}
			node = node->child_[c];
		}
		node->bend_ = true;
		node->rule_obj_ = rule_obj;
	}

	void printf_root()
	{
		auto node = root_;
		std::string tmp;
		for (auto& pair : node->child_) {
			tmp.push_back(pair.first);
			tmp.append(" ");
		}
		for (size_t i = 0; i < rules_.size(); ++i) {
			MY_PRINT("rule%zd:%s", i, rules_[i].c_str());
		}
		MY_PRINT("root child is:%s", tmp.c_str());
	}

	// 匹配域名并返回匹配的规则名
	bool match_domain(const std::string& domain, void** value)
	{
		if (domain.empty()) {
			return false;
		}
		ENTER_FUNCTION;
		bool bret =  match(root_, domain.c_str(), value);
		EXIT_FUNCTION;
		return bret;
	}

private:
	// 模糊查询
	bool fuzzy_match(
			std::shared_ptr<dp_trie_node>& node, const char* domain, void** value)
	{
		if(NULL==node) {
			MY_PRINT("dn=%s, node=%p",  domain);
			return false;
		}

		int max_len = strlen(domain);
		std::string tmp;
		node->get_tree_str(tmp);
		MY_PRINT("dn=%s, node=%s", domain, tmp.c_str());
		for (auto it = node->child_.begin(); it != node->child_.end(); ++it) {
			const char* tmp_pos = strchr(domain, it->first);
			while (tmp_pos) {
				//MY_PRINT("key=%c, size=%lu, tmp_pos=%s, maxlen=%d, dif=%d", it->first, node->child_.size(), tmp_pos, max_len, tmp_pos-domain);
				ENTER_FUNCTION;
				bool bm = match(it->second, tmp_pos + 1, value);
				EXIT_FUNCTION;
				if (bm) {
					MY_PRINT("dn=%s, node=%s",domain, tmp.c_str());
					return true;
				}
				int next_start = (tmp_pos - domain) + 1;
				tmp_pos = strchr(tmp_pos + 1, it->first);
				if(next_start==max_len) { // 单字符最后一个匹配 xxx6 匹配到*6
					if (value) {
						*value = it->second->rule_obj_;
					}
					MY_PRINT("dn=%s, node=%s",domain, tmp.c_str());
					return true;
				}
			}
		}
		if(node->bend_) {
			if (value) {
				*value = node->rule_obj_;
			}
			return true;
		}
		MY_PRINT("dn=%s, node=%s", domain, tmp.c_str());
		return false;
	}

	bool match(std::shared_ptr<dp_trie_node>& node_s, const char* domain, void** value)
	{
		if (NULL == domain || 0 == *domain || NULL == node_s) {
			return false;
		}
		int dn_pos = 0;
		size_t dn_len = strlen(domain);
		auto node = node_s;
		do {
			char c = domain[dn_pos];
			if (node->child_.find(c) != node->child_.end()) {
				node = node->child_[c];
				dn_pos++;
				MY_PRINT("c=%c", c);
			} else if (node->child_.find('?') != node->child_.end()) {
				node = node->child_['?'];
				dn_pos++;
				MY_PRINT("c=%c",c);
			} else if (node->child_.find('*') != node->child_.end()) {
				node = node->child_['*'];
				//std::string tmp;
				//if(node) {
				//	node->get_tree_str(tmp);
				//}
				//MY_PRINT("c=%c,pos=%d,dn=%s node=%s", c, dn_pos,domain, tmp.c_str());
				// 继续往下匹配，直到找到规则的结尾
				ENTER_FUNCTION;
				bool bf = fuzzy_match(node, domain + dn_pos, value);
				EXIT_FUNCTION;
				MY_PRINT("c=%c, bf=%d", c, bf);
				if (bf) {
					return true;
				}
				break;
			} else {
				// 查找上一级的是否存在*或?
				int tmp_deep = dn_pos - 1;
				auto node_p = node->parent_;
				if(node_p) {
					std::string r;
					node_p->get_tree_str(r);
					MY_PRINT("c=%c, dep=%d, dn=%s p=%s, start=%s", c, tmp_deep, domain + tmp_deep,r.c_str(), domain);
				} else {
					MY_PRINT("c=%c, dep=%d, start=%s", c, tmp_deep, domain);
				}
				while (tmp_deep >= 0 && node_p) {
					void* ret = NULL;
					std::shared_ptr<dp_trie_node> tmp_node;
					std::string r;
					node_p->get_tree_str(r);
					if(node_p->child_.find('?') != node_p->child_.end()) {
						tmp_node = node_p->child_['?'];
						ENTER_FUNCTION;
						bool bf = fuzzy_match(tmp_node, domain + tmp_deep, value);
						EXIT_FUNCTION;
						MY_PRINT("c=%c, dep=%d, p=%s, start=%s",  c, tmp_deep, r.c_str(), domain);
						if(bf) {
							return true;
						}
					} else {
						MY_PRINT("c=%c, dep=%d, p=%s, start=%s", c, tmp_deep, r.c_str(), domain);
					}
					if(node_p->child_.find('*') != node_p->child_.end()) {
						tmp_node = node_p->child_['*'];
						ENTER_FUNCTION;
						if(NULL==node_p->parent_) {
							MY_PRINT("@@@ depp=%d, r=%s, tmp_node=%p", tmp_deep, r.c_str(), tmp_node.get());
						}
						bool bf = fuzzy_match(tmp_node, domain + tmp_deep, value);
						EXIT_FUNCTION;
						MY_PRINT("c=%c, dep=%d, p=%s, start=%s", c, tmp_deep, r.c_str(), domain);
						if(bf) {
							return true;
						}
					} else {
						MY_PRINT("c=%c, dep=%d, p=%s, start=%s", c, tmp_deep, r.c_str(), domain);
					}
					tmp_deep--;
					node_p = node_p->parent_;
				}
				MY_PRINT("c=%c, dep=%d", c, tmp_deep);
				return false; // 没有匹配的路径
			}
		} while (dn_pos < dn_len);

		// 检查最终节点是否是一个规则的结尾
		if (node && node->bend_) {
			if (value) {
				*value = node->rule_obj_;
			}
			return true;
		} else {
			return false;
		}
	}

private:
	std::shared_ptr<dp_trie_node> root_;
	std::vector<std::string> rules_;
};

void test_print(dp_trie& trie, const std::string& domain, bool succ=true)
{
	std::string* str = NULL;
	bool bret = trie.match_domain(domain, (void**)&str);
	if (bret==succ) {
		printf("\033[32mSuccess test %smatch\033[0m, Domain=%s, Rule='%s'\n", bret?"full_":"miss_", domain.c_str(), NULL==str?"NULL":str->c_str());
	} else {
		printf("\033[31;1mFailed test %smatch\033[0m, Domain='%s'\n", succ?"full_":"miss_",domain.c_str());
	}
}


std::vector<std::string>  get_base_rules() {
	std::vector<std::string> rules;
	rules.push_back("*.example.com");
	rules.push_back("test?.org");
	rules.push_back("test??.org");
	rules.push_back("xyz*");
	rules.push_back("www.example.com");
	rules.push_back("*xyz*");
	rules.push_back("abc*xyz");
	rules.push_back("abc.net");
	rules.push_back("test*.org");
	rules.push_back("*6");
	rules.push_back("d*");
	rules.push_back("7");
	return rules;
}

// 基础匹配测试
void base_test()
{
    dp_trie trie;
	auto rules = get_base_rules();
	for(int i=0; i<rules.size(); ++i) {
		const std::string & v = rules[i];
		trie.insert(v, (void*)&v);
	}
    trie.printf_root();
    // 多字符全匹配测试
    test_print(trie, "abc.xyz..example.com");
    test_print(trie, "test1.org");
    test_print(trie, "test12.org");
    test_print(trie, "test.org");
    test_print(trie, "xyz.net");
    test_print(trie, "www.example.com");
    test_print(trie, "mmm.xyz.xxx");
    test_print(trie, "abc.mmm.qqqq.xyz");

	// 单字符前后缀匹配测试
	test_print(trie, "tv_122770c3a2c2f35c5d649264f4faf03e_1502247629576");
    test_print(trie, "dv_xxx");
    test_print(trie, "7");

	// 匹配失败测试
    test_print(trie, "invalid.com", false);
}

// 根节点为*测试
void root_test()
{
    dp_trie trie;
	auto rules = get_base_rules();
	rules.push_back("*");
	for(int i=0; i<rules.size(); ++i) {
		const std::string & v = rules[i];
		trie.insert(v, (void*)&v);
	}
    trie.printf_root();
	if(1) {
		// 多字符全匹配测试
		test_print(trie, "abc.xyz..example.com");
		test_print(trie, "test1.org");
		test_print(trie, "test12.org");
		test_print(trie, "test.org");
		test_print(trie, "xyz.net");
		test_print(trie, "www.example.com");
		test_print(trie, "mmm.xyz.xxx");
		test_print(trie, "abc.mmm.qqqq.xyz");

		// 单字符前后缀匹配测试
		test_print(trie, "tv_122770c3a2c2f35c5d649264f4faf03e_1502247629576");
		test_print(trie, "dv_xxx");
		test_print(trie, "7");

		// 匹配失败测试
		test_print(trie, "invalid.com", true);
	}
		//test_print(trie, "abc.xyz..example.com");

}

int main()
{
	//base_test();
	root_test();
	return 0;
}
